package com.tucc.hello.leetcode.no401_800.no494;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1};
        int target = 1;
        System.out.println(solution.findTargetSumWays(nums, target));
    }

    public int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        findTargetSumWays(nums, 0, target, 0);
        return count;
    }

    public void findTargetSumWays(int[] nums, int curIndex, int target, int curSum) {
        if (curIndex == nums.length) {
            if (target == curSum) {
                count++;
            }
        } else {
            findTargetSumWays(nums, curIndex + 1, target, curSum + nums[curIndex]);
            findTargetSumWays(nums, curIndex + 1, target, curSum - nums[curIndex]);
        }
    }
}
